home *** CD-ROM | disk | FTP | other *** search
/ Oh!X 2001 Spring / Oh!X 2001 Spring Special CD-ROM (Japan).7z / Oh!X 2001 Spring Special CD-ROM (Japan) (Track 1).bin / PUZZLE / Puz02 / hex2.c < prev    next >
C/C++ Source or Header  |  2000-06-28  |  3KB  |  160 lines
  1. /*
  2.  * hex2.c : パズル「ヘックス」 15 パズルの変形バージョン
  3.  *
  4.  *          初期状態と最終状態の両方から検索する
  5.  */
  6. /*
  7.  
  8.          １------２
  9.        ／  ＼  ／  ＼
  10.      ３------４------５
  11.        ＼  ／  ＼  ／ 
  12.          ６------０
  13.  
  14. 座標
  15.          ０------１
  16.        ／  ＼  ／  ＼
  17.      ２------３------４
  18.        ＼  ／  ＼  ／ 
  19.          ５------６
  20. */
  21. #include <stdio.h>
  22. #include <string.h>
  23. #include <time.h>
  24.  
  25. #define TRUE  1
  26. #define FALSE 0
  27. #define SIZE  7
  28. #define FORWARD  0
  29. #define BACKWARD 1 
  30.  
  31. /* 最大の状態数 7! = 5040 */
  32. #define MAX_STATE 5040
  33.  
  34. /* 隣接リスト */
  35. const char adjacent[SIZE][7] = {
  36.   1, 2, 3, -1, -1, -1, -1,  /* 0 */
  37.   0, 3, 4, -1, -1, -1, -1,  /* 1 */
  38.   0, 3, 5, -1, -1, -1, -1,  /* 2 */
  39.   0, 1, 2,  4,  5,  6, -1,  /* 3 */
  40.   1, 3, 6, -1, -1, -1, -1,  /* 4 */
  41.   2, 3, 6, -1, -1, -1, -1,  /* 5 */
  42.   3, 4, 5, -1, -1, -1, -1   /* 6 */
  43. };
  44.  
  45. /* キュー */
  46. char  state[MAX_STATE + 1][SIZE];      /* +1 はワーク領域 */
  47. char  space_postion[MAX_STATE];
  48. short prev_state[MAX_STATE];
  49. char  direction[MAX_STATE];
  50.  
  51.  
  52. /* 初期状態 */
  53. char init_state[SIZE] = {
  54.   1, 5, 2, 6, 3, 4, 0
  55. };
  56.  
  57. /* 最終状態 */
  58. char final_state[SIZE] = {
  59.   1, 2, 3, 4, 5, 6, 0
  60. };
  61.  
  62. /* 同じ状態があるか */
  63. int check_same_state( int n )
  64. {
  65.   int i;
  66.   for( i = 0; i < n; i++ ){
  67.     if( !memcmp( state[i], state[n], SIZE ) ) return i;
  68.   }
  69.   return -1;
  70. }
  71.  
  72. /* 結果を出力 */
  73. void print_answer_forward( int n )
  74. {
  75.   int i;
  76.   if( n > 1 ) print_answer_forward( prev_state[n] );
  77.   for( i = 0; i < SIZE; i++ ){
  78.     printf("%d ", state[n][i] );
  79.   }
  80.   printf("\n");
  81. }
  82.  
  83. void print_answer_backward( int n )
  84. {
  85.   do {
  86.     int i;
  87.     n = prev_state[n];
  88.     for( i = 0; i < SIZE; i++ ){
  89.       printf("%d ", state[n][i] );
  90.     }
  91.     printf("\n");
  92.   } while( prev_state[n] != -1 );
  93. }
  94.  
  95. void print_answer( int i, int j )
  96. {
  97.   if( direction[i] == FORWARD ){
  98.     print_answer_forward( i );
  99.     print_answer_backward( j );
  100.   } else {
  101.     print_answer_forward( j );
  102.     print_answer_backward( i );
  103.   }
  104. }
  105.  
  106. /* 探索 */
  107. void search( void )
  108. {
  109.   int front = 0, rear = 2;
  110.   /* 初期化 */
  111.   memcpy( state[0], init_state, SIZE );
  112.   space_postion[0] = 6;
  113.   prev_state[0] = -1;
  114.   direction[0] = FORWARD;
  115.   memcpy( state[1], final_state, SIZE );
  116.   space_postion[1] = 6;
  117.   prev_state[1] = -1;
  118.   direction[1] = BACKWARD;
  119.   while( front < rear ){
  120.     int s = space_postion[front];
  121.     int i, j, n;
  122.     for( i = 0; (n = adjacent[s][i]) != -1; i++ ){
  123.       /* 状態をコピー */
  124.       memcpy( state[rear], state[front], SIZE );
  125.       /* 移動 */
  126.       state[rear][s] = state[rear][n];
  127.       state[rear][n] = 0;
  128.       space_postion[rear] = n;
  129.       prev_state[rear] = front;
  130.       direction[rear] = direction[front];
  131.       /* 検索する */
  132.       if( (j = check_same_state( rear )) >= 0 ){
  133.     if( direction[j] != direction[rear] ){
  134.       /* 前後からの検索が一致 */
  135.       print_answer( j, rear );
  136.       printf("状態数 %d 個\n", rear );
  137.       return;
  138.     }
  139.       } else {
  140.     /* 登録 */
  141.     rear++;
  142.       }
  143.     }
  144.     front++;
  145.   }
  146. }
  147.  
  148. int main()
  149. {
  150.   int start, end;
  151.   start = clock();
  152.   search();
  153.   end = clock();
  154.   printf("時間 %d \n",end - start );
  155.   return 0;
  156. }
  157.  
  158. /* end of file */
  159.  
  160.